package com.LeeCode;

/**
 * 统计水平子串和垂直子串重叠格子的数目
 */

public class Code3529 {
    public static void main(String[] args) {

    }

    public int countCells(char[][] grid, String pattern) {
        int m = grid.length;
        int n = grid[0].length;

        char[] hText = new char[m * n];
        int idx = 0;
        for (char[] row : grid) {
            for (char c : row) {
                hText[idx++] = c;
            }
        }

        char[] vText = new char[m * n];
        idx = 0;
        for (int j = 0; j < n; j++) {
            for (char[] row : grid) {
                vText[idx++] = row[j];
            }
        }

        char[] pat = pattern.toCharArray();
        int[] pi = calcPi(pat);
        int[] inPatternH = kmpSearch(hText, pat, pi);
        int[] inPatternV = kmpSearch(vText, pat, pi);

        int ans = 0;
        for (int i = 0; i < m * n; i++) {
            if (inPatternH[i] > 0 && inPatternV[i % n * m + i / n] > 0) {
                ans++;
            }
        }
        return ans;
    }

    private int[] calcPi(char[] pattern) {
        int[] pi = new int[pattern.length];
        int match = 0;
        for (int i = 1; i < pi.length; i++) {
            char b = pattern[i];
            while (match > 0 && pattern[match] != b) {
                match = pi[match - 1];
            }
            if (pattern[match] == b) {
                match++;
            }
            pi[i] = match;
        }
        return pi;
    }

    private int[] kmpSearch(char[] text, char[] pattern, int[] pi) {
        int n = text.length;
        int[] diff = new int[n + 1];
        int match = 0;
        for (int i = 0; i < n; i++) {
            char b = text[i];
            while (match > 0 && pattern[match] != b) {
                match = pi[match - 1];
            }
            if (pattern[match] == b) {
                match++;
            }
            if (match == pi.length) {
                diff[i - pi.length + 1]++;
                diff[i + 1]--;
                match = pi[match - 1];
            }
        }
        for (int i = 1; i < n; i++) {
            diff[i] += diff[i - 1];
        }
        return diff;
    }
}
